package com.le.high.class3;

import org.junit.Test;

/**
 * 给定一棵二叉树的头节点head，可以从树中的【任何一点】出发，
 * 如果走的话只能向下， 也可以选择随时停止，
 * 所形成的轨迹叫做一条路径，路径上所有值的累加和叫作路径 和。
 * 求这棵树上的最大路径和。
 */
public class Problem01_MaxPathSumInBT {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int val) {
            value = val;
        }
    }

    public static int maxPathSum(Node head) {
        if (head == null) {
            return 0;
        }
        Info info = process(head);
        return info.maxVal < 0 ? info.maxVal : info.maxSumAll;
    }

    public static class Info {
        int maxVal; // 整棵树中最大值
        int maxSumHead;
        int maxSumAll;

        public Info(int maxVal, int maxSumHead, int maxSumAll) {
            this.maxVal = maxVal;
            this.maxSumHead = maxSumHead;
            this.maxSumAll = maxSumAll;
        }
    }

    public static Info process(Node x) {
        if (x == null) {
            return new Info(Integer.MIN_VALUE, 0, 0);
        }
        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);
        int maxVal = Math.max(x.value, Math.max(leftInfo.maxVal, rightInfo.maxVal));
        int maxSumHead = Math.max(leftInfo.maxSumHead, rightInfo.maxSumHead) + x.value;
        maxSumHead = Math.max(maxSumHead, x.value);
        int maxSumAll = Math.max(maxSumHead, Math.max(leftInfo.maxSumAll, rightInfo.maxSumAll));
        return new Info(maxVal, maxSumHead, maxSumAll);
    }


    @Test
    public void test() {
        Node head1 = new Node(-7);
        head1.left = new Node(-7);
        head1.right = new Node(-7);
        head1.left.left = new Node(3);
        head1.right.left = new Node(-7);
        head1.left.left.left = new Node(2);
        System.out.println(maxPathSum(head1));


        Node head2 = new Node(-7);
        head2.left = new Node(-6);
        head2.right = new Node(-5);
        head2.left.left = new Node(-3);
        head2.right.left = new Node(-4);
        head2.left.left.left = new Node(-2);
        System.out.println(maxPathSum(head2));
    }
}
